Uniformly Random Hash Function

Definition

A random function $h: \mathcal{U} \rightarrow \{1, ... , m\}$ is called uniformly random if:

• $\mathrm{Pr}[h(x)=i]=\frac{1}{m}$ for all $x \in \mathcal{U}$, $i \in \{1,...,m\}$
• $h(x)$ and $h(y)$ are independent r.v.'s for all $x,y \in \mathcal{U}$
  • which implies $\mathrm{Pr}[h(x)=h(y)]=\frac{1}{m}$

See also

• Hashing.
• Compare: Universal hash function.